package problems.contest;

import java.util.HashSet;
import java.util.Set;

/**
 * @author dubulingbo, 2023/6/4 10:29.
 */
public class WCT348 {
    /**
     * T1|6462. 最小化字符串长度
     */
    public int minimizedStringLength(String s) {
        char[] chs = s.toCharArray();
        boolean[] ex = new boolean[26];
        for (char c : chs) ex[c - 'a'] = true;

        int ret = 0;
        for (boolean e : ex) {
            if (e) ++ret;
        }

        return ret;
    }


    /**
     * T2|6424. 半有序排列
     */
    public int semiOrderedPermutation(int[] nums) {
        int n = nums.length;
        int maxIdx = -1;
        int minIdx = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] == 1) minIdx = i;
            else if (nums[i] == n) maxIdx = i;
        }

        int ans = minIdx + n - 1 -maxIdx;
        return minIdx < maxIdx ? ans : ans - 1;
    }

    /**
     * T3|6472. 查询后矩阵的和
     * <p style="color:red">超出内存限制</p>
     */
    public long matrixSumQueries1(int n, int[][] queries) {
        int[][] matrix = new int[n][n];

        long ret = 0L;

        for (int[] q : queries) {
            int k = q[1];
            int v = q[2];
            if (q[0] == 0) {
                // 行
                for (int i = 0; i < n; ++i) {
                    ret += (v - matrix[k][i]);
                    matrix[k][i] = v;
                }
            } else {
                for (int i = 0; i < n; ++i) {
                    ret += (v - matrix[i][k]);
                    matrix[i][k] = v;
                }
            }
        }
        return ret;
    }

    public long matrixSumQueries(int n, int[][] queries) {
        // 分别定义行，列hash表，记录已经操作过的行、列的序号
        Set<Integer>[] sets = new Set[] {new HashSet<Integer>(), new HashSet<Integer>()};
        long ret = 0L;

        // 从后往前遍历 queries
        for (int i = queries.length - 1; i >= 0; --i) {
            // 之后没有操作过该行或列
            int typ = queries[i][0];
            int k = queries[i][1];
            if (!sets[typ].contains(k)) {
                ret += (long) (n - sets[typ ^ 1].size()) * queries[i][2];
                sets[typ].add(k);
            }
        }
        return ret;
    }
}
